package cs235.sort;

public class InsertionSort extends TannersSort implements Sort{
    
    
    public InsertionSort(){
        compares = 0;
    }
    
    
    /**
     * Simple insertion sort.
     * @param a an array of Comparable items.
     */
    public static void insertionSort( Comparable [ ] a )
    {
        for( int p = 1; p < a.length; p++ )
        {
            Comparable tmp = a[ p ];
            int j = p;

            for( ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }

    @Override
    public void sort(Comparable[] a) {
        compares = 0;
        for( int p = 1; p < a.length; p++ )
        {
            Comparable tmp = a[ p ];
            int j = p;
            boolean enteredLoop = false;
            int compare=-1;
            for( ; j > 0 && (compare = tmp.compareTo( a[ j - 1 ] )) < 0; j-- ){
                a[ j ] = a[ j - 1 ];
                ++compares;
                enteredLoop = true;
            } 
            if (!enteredLoop || compare >= 0){
                ++compares;
            }
            a[ j ] = tmp;
        }
    }

}
